home *** CD-ROM | disk | FTP | other *** search
/ Internet Info 1994 March / Internet Info CD-ROM (Walnut Creek) (March 1994).iso / networking / info-service / wais / ir-book-sources / thesauri / select.c < prev   
Encoding:
C/C++ Source or Header  |  1993-04-08  |  39.7 KB  |  1,086 lines
  1. /*
  2.    PROGRAM NAME:  select.c
  3.  
  4.    PURPOSE:  1) Compute Discrimination Value of terms, 
  5.              2) Compute Poisson Distributions for terms,
  6.              3) Parition terms by their total within document frequencies,
  7.              4) Compute cohesion between pairs of terms,
  8.              5) Compute Dice's coefficient of similarity between two terms.
  9.  
  10.    INPUT FILES REQUIRED:
  11.  
  12.              1) a direct file, sequences of:
  13.  
  14.                 document#    term    weight
  15.  
  16.                 (multiple entries for any document should be grouped together )
  17.  
  18.              2) an inverted file, sequences of
  19.  
  20.                 term     document#    weight
  21.  
  22.                 (multiple entries for any term should be grouped together)
  23.    
  24.    NOTES:    Filters such as stop lists and stemmers should be used before
  25.              before running this program.
  26.  
  27.    PARAMETERS TO BE SET BY USER:
  28.  
  29.              1) MAXWORD - maximum size of a term
  30.              2) MAXWDF  - maximum value expected for the within document
  31.                           frequency for a term in the collecgtion.
  32.              3) LOW_THRESHOLD - threshold for LOW and MID frequency ranges
  33.              4) HIGH_THRESHOLD - threshold for MID and HIGH frequency ranges
  34.  
  35.    COMMAND LINE:
  36.  
  37.              select direct_file inverted_file output_file
  38.  
  39. ****************************************************************************/
  40.  
  41. #include <stdio.h>
  42. #include <string.h>
  43. #include <math.h>
  44. #define MAXWORD 20          /* maximum size of a term                  */
  45. #define MAXWDF 30           /* maximum WDF for a word in a database    */
  46. #define LOW_THRESHOLD 2.0
  47. #define HIGH_THRESHOLD 4.0
  48.  
  49. struct termlist {           /* sequences of term and weight pairs      */
  50.   char term[MAXWORD];       /* term                                    */
  51.   float weight;             /* term weight in document                 */
  52.   struct termlist *nextterm;/* ptr. to next termlist record            */
  53. } termlistfile;
  54.  
  55. struct doclist {            /* sequences of document # and weight pairs*/
  56.   int doc;                  /* document number                         */
  57.   float weight;             /* term weight in document                 */
  58.   struct doclist *nextdoc;  /* ptr. to next doclist record             */
  59. } doclistfile;
  60.  
  61. struct direct {             /* direct file: document to list of terms  */
  62.   int docnum;               /* document #                              */
  63.   struct termlist *terms;   /* sequences of term and weight pairs      */
  64.   struct direct *next;      /* ptr. to next direct record              */
  65. } directfile;
  66.  
  67. struct invert {             /* inverted file: term to list of documnts */
  68.   char term[MAXWORD];       /* term                                    */
  69.   struct doclist *doc;      /* sequences of document # and weight pairs*/
  70.   struct invert *next;      /* ptr. to next invert record              */
  71. } invfile;
  72.  
  73. static struct invert *startinv;    /* ptr. to first record in inverted file   */
  74. static struct invert *lastinv;     /* ptr. to last record in inverted file    */
  75. static struct doclist *lastdoc;    /* ptr. to last document in doclist        */
  76. static struct direct *startdir;    /* ptr. to first record in direct file     */
  77. static struct direct *lastdir;     /* ptr. to last record in direct file      */
  78. static struct termlist *lastterm;  /* ptr. to last term in termlist           */
  79. static struct direct *start_centroid; /* ptr. to centroid record              */
  80.  
  81. static FILE *input;                /* direct file                             */
  82. static FILE *input1;               /* inverted file                           */
  83. static FILE *output;               /* file to hold all output                 */
  84.  
  85. static int currentdoc;             /* tracks current document in direct file  */
  86. static char currentterm[MAXWORD];  /* tracks current term in inverted file    */
  87. static int Number_of_docs;         /* total # of documents which is computed  */
  88.  
  89. static
  90. float av_doc_similarity(),   /* compute average doc. similarity in dbse. */
  91.       factorial(),           /* compute factorial of a number            */ 
  92.       cosine(),              /* compute cosine between two terms         */
  93.       dice(),                /* compute dice beteen two terms            */
  94.       total_wdf(),          /* compute total frequency of term in dbse. */
  95.       cohesion();            /* compute cohesion between two terms       */
  96. static
  97. void initialize(),           /* initialize files and global variables    */
  98.      read_directfile(),      /* read in the direct file                  */
  99.      add_direct(),           /* called within read_directfile()          */
  100.      pr_direct(),            /* print the direct file                    */
  101.      read_invfile(),         /* read in the inverted file                */
  102.      add_invert(),           /* called within read_invfile()             */
  103.      pr_invert(),            /* print the inverted file                  */
  104.      centroid(),             /* compute the document centroid for dbse.  */
  105.      pr_centroid(),          /* print the document centroid              */
  106.      get_Poisson_dist(),     /* compute Poisson distributions for terms  */
  107.      Partition_terms(),      /* partition terms by frequency             */
  108.      dv_all(),               /* compute discrimination value of terms    */
  109.      get_doc_data(),           /* get basic info. about documents          */
  110.      get_term_data();          /* get basic info. about terms              */
  111.  
  112. static struct direct *get_mem_direct();     /* these 4 get_mem functions are */
  113. static struct invert *get_mem_invert();     /* used to obtain memory for a   */
  114. static struct doclist *get_mem_doclist();   /* record. The record type is    */
  115. static struct termlist *get_mem_termlist(); /* obvious from the name         */
  116.  
  117. struct invert *find_term();         /* searches for term in inverted file*/
  118.                                     /* and returns its address           */
  119. int main(argc,argv)
  120. int argc;
  121. char *argv[];
  122. {
  123.  
  124. char ch, word1[MAXWORD], word2[MAXWORD];
  125.  
  126. if (argc!=4) 
  127.   {
  128.   (void) printf("There is an error in the command line\n");
  129.   (void) printf("Correct usage is\n");
  130.   (void) printf("select direct_file inverted_file output_file\n");
  131.   exit(1);
  132.   }
  133.  
  134. initialize(argv);
  135. (void) fprintf(output,"\nREADING IN DIRECT FILE\n");
  136. read_directfile();
  137. (void) fprintf(output,"\nPRINTING DIRECT FILE\n\n");
  138. pr_direct();
  139. (void) fprintf(output,"\nNUMBER OF DOCUMENTS IS: %d\n\n",Number_of_docs);
  140. (void) fprintf(output,"\nREADING IN INVERTED FILE\n");
  141. read_invfile();
  142. (void) fprintf(output,"\nPRINTING INVERTED FILE\n");
  143. pr_invert();
  144.  
  145. (void) printf("\nPlease make a selection\n\n");
  146. (void) printf("To compute DV for all terms enter 1\n");
  147. (void) printf("To compute Poisson distributions enter 2\n");
  148. (void) printf("To partition terms by frequency enter 3\n");
  149. (void) printf("To compute cohesion between two terms (for phrase construction) enter 4\n");
  150. (void) printf("To compute Dice's coefficient between two terms enter 5\n");
  151. (void) printf("To quit enter 6\n\n");
  152. (void) printf("Enter your choice: ");
  153. ch = getchar();
  154.    switch(ch)
  155.       {
  156.       case '1':
  157.           centroid();
  158.           (void) fprintf(output,"\nCENTROID\n\n");
  159.           pr_centroid();
  160.           (void) fprintf(output,"\nDISCRIMINATION VALUES FOR ALL TERMS\n\n");
  161.           dv_all();
  162.           break;
  163.       case '2':
  164.           (void) fprintf(output,"\nACTUAL AND POISSON DISTRIBUTIONS OF WITHIN DOCUMENT FREQUENCIES FOR ALL TERMS\n\n");
  165.           (void) fprintf(output,"WDF = Within Document Frequency & #docs = Number of documents\n\n");
  166.           get_Poisson_dist();
  167.           break;
  168.       case '3':
  169.           (void) printf("Make sure that the threshold parameters are set correctly in the programm\n");
  170.           (void) fprintf(output,"\nPARTITIONING THE TERMS INTO LOW, MEDIUM, HIGH FREQUENCY CLASSES\n\n");
  171.           Partition_terms();
  172.           break;
  173.       case '4':
  174.           (void) printf("enter first word: ");
  175.           (void) scanf("%s",word1);
  176.           if (find_term(word1) == NULL) {
  177.                printf("sorry, %s is not in the inverted file\n",word1);
  178.                break;
  179.           }
  180.           (void) printf("enter second word: ");
  181.           (void) scanf("%s",word2);
  182.           if (find_term(word2) == NULL) {
  183.                printf("sorry, %s is not in the inverted file\n",word2);
  184.                break;
  185.           }
  186.           (void) fprintf(output,"Cohesion between %s and %s is %f\n",word1,word2,cohesion(word1,word2));
  187.           break;
  188.       case '5':
  189.           (void) printf("enter first word: ");
  190.           (void) scanf("%s",word1);
  191.           if (find_term(word1) == NULL) {
  192.                printf("sorry, %s is not in the inverted file\n",word1);
  193.                break;
  194.           }
  195.           (void) printf("enter second word: ");
  196.           (void) scanf("%s",word2);
  197.           if (find_term(word2) == NULL) {
  198.                printf("sorry, %s is not in the inverted file\n",word2);
  199.                break;
  200.           }
  201.           (void) fprintf(output,"Dice's coefficient between %s and %s is %f\n",word1,word2,dice(word1,word2));
  202.           break;
  203.       case '6':
  204.           exit(0);
  205.       default:
  206.           (void) printf("no selection made\n");
  207.       }
  208.  
  209. (void) fclose(input1); (void) fclose(input); (void) fclose(output);
  210. return(0);
  211.  
  212. }
  213. /****************************************************************************
  214.  
  215.     initialize(argv)
  216.  
  217.     Returns:  void
  218.  
  219.     Purpose:  Open all required files and initialize global variables 
  220.  
  221. **/
  222.  
  223. static void initialize(argv)
  224. char *argv[];   /* in: holds the three parameters input at the command line */
  225. {
  226. if (( input = fopen(argv[1],"r")) == NULL ) {
  227.    (void) printf("couldn't open file %s\n",argv[1]);
  228.    exit(1); /* input direct file */
  229. }
  230. if (( input1 = fopen(argv[2],"r")) == NULL ) {
  231.    (void) printf("couldn't open file %s\n",argv[2]);
  232.    exit(1); /* input inverted file */
  233. }
  234. if (( output = fopen(argv[3],"w")) == NULL) {
  235.    (void) printf("couldn't open file %s for output\n",argv[3]);
  236.    exit(1); /* output file */
  237. }
  238. /* set initial values of global variables */
  239. startinv = NULL; lastinv = NULL;  lastdoc = NULL;
  240. startdir = NULL;  lastdir = NULL;  lastterm = NULL;
  241. start_centroid = NULL;
  242. currentdoc = 0;   currentterm[0] = '\0';  Number_of_docs = 0;
  243. }
  244.  
  245. /****************************************************************************/
  246. /* 
  247.    read_directfile()
  248.  
  249.    Returns:  void
  250.  
  251.    Purpose:  Read in the direct file entries from the 1st input file 
  252.  
  253. **/
  254.  
  255. static void read_directfile()
  256. {
  257. int docid;            /* holds the current document number       */
  258. char temp[MAXWORD];   /* holds the current term                  */
  259. float weight;         /* holds the current term weight           */
  260. struct termlist *p;   /* structure to store the term-weight pair */
  261.  
  262. (void) fscanf(input,"%d%s%f",&docid,temp,&weight); /* read the next line */
  263. while (docid > 0)  
  264.       /* while its found a legitimate document number               */
  265. {
  266. if (docid == currentdoc) { 
  267.       /* if this document number has previously been entered in direct file */
  268.       /* then only need to attach a termlist record to the same entry   */
  269.    p = get_mem_termlist();   /* get memory for a termlist record */
  270.    (void) strncpy(p->term,temp,MAXWORD);  /* copy the new word over */
  271.    p->weight = weight;             /* assign the new weight over */
  272.    p->nextterm = NULL;             
  273.    if (lastterm) lastterm->nextterm = p; /* connect p to the termlist
  274.                                chain for this document */
  275.    lastterm = p;    /* set this global variable */
  276. }
  277. else {  /* else docid represents a new document */
  278.   Number_of_docs = Number_of_docs +1;  /* increment global variable */
  279.   add_direct(docid,temp,weight); /* starts a brand new entry in */
  280.                  /* the direct file             */
  281. }
  282. docid = 0;
  283. (void) fscanf(input,"%d%s%f",&docid,temp,&weight);
  284. }
  285. }
  286. /***************************************************************************
  287.  
  288.    add_direct(docid,temp,weight)
  289.  
  290.    Returns:  void
  291.   
  292.    Purpose:  Start a new entry in the direct file.  It is called in
  293.              the read_directfile function when a new document number is
  294.              read from the input file.
  295. **/
  296.  
  297. static void add_direct(docid,temp,weight)
  298. int docid;              /* in: new document number                   */
  299. char temp[MAXWORD];     /* in: index term                            */
  300. float weight;           /* in: index term weight                     */
  301. {
  302. struct direct *p;       /* structure p will be attached to direct file */
  303.  
  304. p = get_mem_direct();    /* get memory for p  */
  305. p->docnum = docid;      /* assign the document number  */
  306. p->terms = get_mem_termlist();  /* get memory for termlist structure  */
  307. (void) strncpy(p->terms->term,temp,MAXWORD); /* assign index term to it     */
  308. p->terms->weight = weight;            /* assign term weight to it    */
  309. p->terms->nextterm = NULL;            /* current end of termlist */
  310. p->next = NULL;                       /* current end of direct file   */
  311. if (startdir == NULL) startdir = p; /* if this is the very first document
  312.     then global variable pointing to start of direct file should be updated */
  313. if (lastdir) lastdir->next = p;  /* update pointer to last direct file rec. */
  314. lastdir = p;
  315. lastterm = p->terms;  /* update pointer to last term */
  316. currentdoc = docid;  /* update the global variable currentdoc to the */
  317.                      /* document number just added                   */
  318. }
  319. /***************************************************************************
  320.      pr_direct()
  321.     
  322.      Returns:  void
  323.  
  324.      Purpose:  Print the direct file.  It prints sequences of
  325.                document#  term  weight.
  326.  
  327. **/
  328.  
  329. static void pr_direct()
  330. {
  331. struct direct *dir_addr;    /* tracks address of current direct file record */
  332. struct termlist *term_addr; /* tracks address of current termlist record    */
  333.  
  334. dir_addr = startdir;  /* start with beginning of direct file           */
  335. while (dir_addr) { /* check for legitimate direct file record          */
  336.   (void) fprintf(output,"DOCUMENT NUMBER: %d  \n",dir_addr->docnum);
  337.   (void) fprintf(output,"                     TERM                           TERM WEIGHT\n");
  338.   term_addr = dir_addr->terms; /* get addr. of first term              */
  339.   while (term_addr) {  /* loop through all the terms                   */
  340.      (void) fprintf(output,"                     %-30s ",term_addr->term);
  341.      (void) fprintf(output,"%-10.3f\n",term_addr->weight);
  342.      term_addr = term_addr->nextterm;  /* go to next term for the doc. */
  343.   }
  344.   (void) fprintf(output,"\n");
  345.   dir_addr = dir_addr->next;   /* go to next direct file record        */
  346. }
  347. }
  348. /***************************************************************************
  349.  
  350.      read_invfile()
  351.      
  352.      Returns:  void
  353.  
  354.      Purpose:  Read in the inverted file entries from 2nd input file 
  355.  
  356. **/
  357.  
  358. static void read_invfile()
  359. {
  360. int docid;          /* holds currenct document number              */
  361. char temp[MAXWORD]; /* holds current term                          */
  362. float weight;       /* holds current term weight                   */
  363. struct doclist *p;  /* structure to store doc#-weight pair         */
  364.  
  365. (void) fscanf(input1,"%s%d%f",temp,&docid,&weight); /* read next line     */
  366. while (strlen(temp) > 0)
  367.       /* while its found a legitimate term                         */
  368. {
  369. if (!strncmp(currentterm,temp,MAXWORD)) { 
  370.     /* if this term has previously been entered in inverted file     */
  371.     /* then only need to attach a doclist record to same term entry  */
  372.    p = get_mem_doclist();  /* get memory for doclist record           */
  373.    p->doc = docid;      /* assign document number */
  374.    p->weight = weight;  /* assign weight          */
  375.    p->nextdoc = NULL;   
  376.    if (lastdoc) lastdoc->nextdoc = p; /* connect p to the doclist 
  377.                           chain for this term  */
  378.    lastdoc = p;  /* set this global variable   */
  379. }
  380. else add_invert(docid,temp,weight);
  381.   /* else term is a brand new term & need to make a new inverted file entry */
  382. temp[0] = '\0';
  383. (void) fscanf(input1,"%s%d%f",temp,&docid,&weight); /* read next line */
  384. }
  385. }
  386. /***************************************************************************
  387.  
  388.     add_invert(docid,temp,weight);
  389.  
  390.     Returns:  void
  391.  
  392.     Purpose:  Start a new entry in the inverted file.  It is called in the
  393.               read_invfile function when a new term is read from the
  394.               input file
  395.  
  396. **/
  397.  
  398. static void add_invert(docid,temp,weight)
  399. int docid;                /* in: document number      */
  400. char temp[MAXWORD];       /* in: new index term       */
  401. float weight;             /* in: index term weight    */
  402. {
  403. struct invert *p;         /* structure p will be attached to inverted file */
  404.  
  405. p = get_mem_invert();      /* get memory for p */
  406. (void) strncpy(p->term,temp,MAXWORD); /* copy over the term  */
  407. p->doc = get_mem_doclist();  /*  start a doclist structure */
  408. p->doc->doc = docid;        /* assign document number     */
  409. p->doc->weight = weight;    /* assign term weight         */
  410. p->doc->nextdoc = NULL;   
  411. p->next = NULL;
  412. if (startinv == NULL) startinv = p;
  413.   /* if this is the first entry in inverted file, then update global var. */
  414. if (lastinv) lastinv->next = p; /* update ptr. to last inverted file record */
  415. lastinv = p; 
  416. lastdoc = p->doc; /* update ptr. to last document */
  417. (void) strncpy(currentterm,temp,MAXWORD); /* update global var. currentterm to the */
  418.                                    /* new term just entered          */
  419. }
  420. /***************************************************************************
  421.  
  422.     pr_invert()
  423.     
  424.     Returns:  void
  425.  
  426.     Purpose:  Print the inverted file.  It prints sequences of
  427.               term  document#  weight.
  428.  
  429. **/
  430.  
  431. static void pr_invert()
  432. {
  433. struct invert *inv_addr; /* tracks address of current inverted file record  */
  434. struct doclist *doc_addr; /* tracks address of current doclist record      */
  435.  
  436. inv_addr = startinv;  /* start with beginning of inverted file */
  437. while (inv_addr) {    /* check for legitimate inverted file record */
  438.   (void) fprintf(output,"TERM: %s\n",inv_addr->term);
  439.   (void) fprintf(output,"                    DOCUMENT NUMBER                TERM WEIGHT\n");
  440.   doc_addr = inv_addr->doc; /* get addr. of first document */
  441.   while (doc_addr) { /*loop through all the associated doc.#s and weights*/ 
  442.      (void) fprintf(output,"                    %-30d ",doc_addr->doc);
  443.      (void) fprintf(output,"%-10.5f\n",doc_addr->weight);
  444.      doc_addr = doc_addr->nextdoc; /* get addr. of next document */
  445.   }
  446.   (void) fprintf(output,"\n");
  447.   inv_addr = inv_addr->next; /* go to next inverted file record */
  448. }
  449. }
  450. /***************************************************************************
  451.   
  452.    centroid()
  453.    
  454.    Returns:  void
  455.  
  456.    Purpose:  Compute and return the centroid for the documents of
  457.              the database. 
  458.  
  459.    Notes:    Centroid is stored as a direct file record.  Document 
  460.              number given to it is Number_of_docs + 1.  The centroid is
  461.              computed by determining for each index term in the inverted
  462.              file, its average weight in the database.  These average
  463.              weights are then stored in the direct file entry for the
  464.              centroid.  (Note that these average weights are not used
  465.              anywhere, but could be used in computing DV for terms).
  466. **/
  467.  
  468. static void centroid()
  469. {
  470. struct invert *inv_addr;  /* tracks address of current inverted file record */
  471. struct doclist *doc_addr; /* tracks address of current doclist record       */
  472. float  total_weight,      /* tracks total weight for each term              */
  473.        av_term_weight;    /* holds average term weight for each term        */
  474. struct termlist *q,       /* structure used to create centroid entry in
  475.                              the direct file                                */
  476.       *lastterm;          /* tracks the last term in the centroid           */
  477.  
  478. start_centroid = get_mem_direct(); /* centroid stored as direct file record  */
  479. start_centroid->docnum = Number_of_docs +1; /* assign its pseudo doc.#      */
  480. start_centroid->next = NULL;  /* end of direct file chain                   */
  481. lastterm = NULL;
  482. inv_addr = startinv;  /* begin at top of inverted file  */
  483. while (inv_addr) {  /* while there is a legitimate inv. file record... */
  484.   doc_addr = inv_addr->doc; /* get address of first document  */
  485.   total_weight = 0.0;  /* start with a 0 total weight for this term */
  486.   while (doc_addr) { /* if this is a legitimate doc. addr. */
  487.     total_weight = total_weight + doc_addr->weight; 
  488.        /* update total weight for term */ 
  489.     doc_addr = doc_addr->nextdoc;  /* loop through all docs. for the term */
  490.   }
  491.   av_term_weight = total_weight/Number_of_docs; 
  492.      /* calculating average term wt. */
  493.   q = get_mem_termlist();
  494.   (void) strncpy(q->term,inv_addr->term,MAXWORD);
  495.   q->weight = av_term_weight;
  496.   q->nextterm = NULL;
  497.   if (lastterm == NULL) start_centroid->terms = q;
  498.      /* if this is the first term entry for the centroid */
  499.     else lastterm->nextterm = q;
  500.      /* else connect this term to the centroid's termlist chain */
  501.   lastterm = q;
  502.   inv_addr = inv_addr->next; /* go on to the next inverted file entry */
  503. }
  504. }
  505. /***************************************************************************
  506.   
  507.      pr_centroid()
  508.  
  509.      Returns:  void
  510.    
  511.      Purpose:  Print the centroid from the direct file
  512.  
  513. **/
  514.  
  515. static void pr_centroid()
  516. {
  517. struct termlist *term_addr;  /* tracks address of current termlist record */
  518.  
  519. /* note the centroid is given a document number = Number_of_docs + 1 */
  520. /* therefore it may be treated as a special kind of document vector  */
  521. if (start_centroid) {
  522.       /* if there is a centroid */
  523.   (void) fprintf(output,"---------------------------------------\n");
  524.   (void) fprintf(output,"TERM                           WEIGHT \n");
  525.   (void) fprintf(output,"---------------------------------------\n");
  526.   term_addr = start_centroid->terms; /* get first term address */
  527.   while (term_addr) { /* printing out term and weight pairs */
  528.      (void) fprintf(output,"%-30s ",term_addr->term);
  529.      (void) fprintf(output,"%-10.5f\n",term_addr->weight);
  530.      term_addr = term_addr->nextterm; /* loop through all terms */
  531.   }
  532.   (void) fprintf(output,"\n");
  533. }
  534. }
  535. /***************************************************************************
  536.      
  537.      get_Poisson_dist()
  538.  
  539.      Returns:  void
  540.  
  541.      Purpose:  Get the Poisson distribution data for any term
  542.  
  543.      Notes:    This function has two parts:
  544.                PART I:  Determine the actual within doc. freq. distribution 
  545.                PART II: Determine the distribution anticipated under the
  546.                         single Poisson model.
  547.                It is assumed that the within document frequency of a term
  548.                is stored as the term weight in the inverted file.
  549.  
  550. **/
  551.  
  552. static void get_Poisson_dist()
  553. {
  554. struct invert *inv_addr;  /* tracks address of current inverted file record */
  555. struct doclist *doc_ad;   /* tracks address of current doclist record       */
  556. float dist[MAXWDF][2];    /* store for each term                            */
  557.                           /* column 1 = within document frequency (wdf)     */
  558.                           /* column 2 = document frequency                  */
  559. int i,                    /* counter to add information to the dist array   */
  560.     j,                    /* counter to loop through dist array             */
  561.     found,                /* flag used to match wdf in dist array           */
  562.     numdocs,              /* counter to track # of docs. with the same wdf  */
  563.     docs_with_term;       /* tracks the number of documents having the term */
  564. float first,              /* these five local variables are                 */
  565.       second,             /* used to determine expected distribution        */
  566.       result, 
  567.       exponent, 
  568.       lambda;             /* single Poisson parameter                       */
  569.  
  570. inv_addr = startinv; /* start at the beginning of the inverted file */
  571.  
  572. /* PART I:  For each term determine the number of documents in the
  573. collection that have a particular wdf */
  574. while (inv_addr) {  /* check for legitimate inv. file record */
  575.   docs_with_term = 0;
  576.   doc_ad = inv_addr->doc;  /* get the first doc. address   */
  577.   i = 0;  /* used to check if this is the very first entry in dist */
  578.   while (doc_ad) {
  579.     if (i == 0) { /* if first entry in dist */
  580.        dist[i][0] = doc_ad->weight;  dist[i][1] = 1;
  581.            /* assign wdf and doc. frequency = 1 to first row in dist */
  582.        i++;
  583.        docs_with_term++;
  584.     }
  585.     else {  /* dist already has other entries, hence look for 
  586.                any previous entries for the same wdf value   */
  587.        found = 0;
  588.        for (j=0;j<i;j++) { /* loop through dist  */
  589.          if (dist[j][0] == doc_ad->weight) { /* if found the same wdf */
  590.              dist[j][1] = dist[j][1] + 1;  /* add 1 to the doc. frequency */
  591.              found = 1; 
  592.              docs_with_term++;
  593.          }
  594.        }  /* ending for */
  595.        if (found == 0) { /* if not found the same wdf in dist */
  596.              /* start new row in dist */
  597.          dist[i][0] = doc_ad->weight;  dist[i][1] = 1;
  598.          i++;
  599.          docs_with_term++;
  600.        }
  601.     }  /* ending else */
  602.   doc_ad = doc_ad->nextdoc;/* loop through other documents for same term */
  603.   }  /* ending while */
  604. /* ending if */
  605.  
  606. /* now print out actual distribution information for this term  */
  607. (void) fprintf(output,"\nTerm = %s\n",inv_addr->term);
  608. (void) fprintf(output,"\nActual Distribution: ");
  609. (void) fprintf(output,"           WDF              #docs\n");
  610. (void) fprintf(output,"                                 0                %d\n",Number_of_docs-docs_with_term);
  611. for (j=0;j<i;j++)
  612.   (void) fprintf(output,"                                 %-16.0f %-6.0f\n",dist[j][0],dist[j][1]);
  613.  
  614. /* PART II:  */
  615. /* computing lambda - the only single Poisson parameter  */
  616.  
  617. (void) fprintf(output,"\nExpected Distribution: ");
  618. (void) fprintf(output,"         WDF              #docs\n");
  619. /* call the function total_wdf to compute the total frequency of the term */
  620. lambda = (total_wdf(inv_addr->term))/Number_of_docs;
  621. first = exp(-lambda);
  622. numdocs = -1; j = -1;
  623. /* computing document frequency for each within document frequency value */
  624. while (numdocs != 0) {
  625.    j = j + 1;
  626.    exponent = j; /* type conversion necessary for pow function */
  627.    if (j == 0) result = first * Number_of_docs;
  628.     else {
  629.       second = pow(lambda,exponent);
  630.       result = (((first * second)/factorial(j)) * Number_of_docs);
  631.    }
  632.    if ((result - floor(result)) < 0.5) numdocs = floor(result); 
  633.       else numdocs = ceil(result);
  634.    (void) fprintf (output,"                                 %-16d %-6d\n",j,numdocs);
  635. }
  636. inv_addr = inv_addr->next; /* continue with the next inverted file term */
  637. } /* end while */
  638. }
  639.  
  640. /***************************************************************************
  641.  
  642.     factorial(n)
  643.  
  644.     Returns:  float 
  645.  
  646.     Purpose:  Return the factorial of a number.  Used in get_poisson_dist
  647.  
  648. **/
  649.  
  650. static float factorial(n)
  651. int n;   /* in:  compute factorial for this parameter */
  652. {
  653. float answer; /* holds the result */
  654.  
  655. if (n==1) return(1.0);
  656. answer = factorial(n-1)*n;
  657. return(answer);
  658. }
  659.  
  660. /***************************************************************************
  661.  
  662.     total_wdf(term)
  663.  
  664.     Returns:  float
  665.  
  666.     Purpose:  Compute total frequency in the database for a specified 
  667.               term using the inverted file.
  668.  
  669.     Notes:    It is assumed that the appropriate term frequency is stored
  670.               as the term weight in the inverted file.  This routine can
  671.               also be used to filter out the low and high frequency terms. 
  672.               The resulting mid frequency terms can be used as input to 
  673.               the program which generates hierarchies.
  674.  
  675. **/
  676.  
  677. static float total_wdf(term)
  678. char term[MAXWORD];   /* in: term for which total frequency is to be found */
  679. {
  680. struct invert *inv_addr;   /* tracks current inverted file record */
  681. struct doclist *doc_addr;  /* tracks current doclist record       */
  682. float total;               /* tracks the total frequency          */
  683.  
  684. total = 0.0;  /* initial value */
  685. /* function find_term will find out where the term is in the inverted file */
  686. inv_addr = find_term(term);
  687. if (inv_addr) { /* if this term was found in the inverted file */
  688.   doc_addr = inv_addr->doc; /* get first associated document address  */
  689.   while (doc_addr) { /* update the total frequency */
  690.     total = total + doc_addr->weight;
  691.     doc_addr = doc_addr->nextdoc;  /* loop through other associated docs. */
  692.   }
  693. }
  694. return(total);
  695. }
  696. /***************************************************************************
  697.  
  698.     Partition_terms()
  699.  
  700.     Returns:  void
  701.  
  702.     Purpose:  Assign each term in the inverted file to one class: 
  703.               HIGH, MEDIUM or LOW frequency depending upon its total 
  704.               frequency in the collection.  This function utilizes
  705.               two parameters defined at the top of the program:
  706.               LOW_THRESHOLD and HIGH_THRESHOLD, which should be set 
  707.               by the user. 
  708.  
  709. **/
  710.  
  711. static void Partition_terms()
  712. {
  713. struct invert *inv_addr;  /* tracks address of current inverted file record */
  714. float total;              /* holds total frequency of each term             */
  715.  
  716. inv_addr = startinv; /* start at the beginning of the inverted file */
  717. (void) fprintf(output,"\nTerm - Total Frequency - Frequency Class\n\n");
  718.  
  719. while (inv_addr) {   /* if a legitimate address */ 
  720.  /* compute total frequency for term in collection */
  721.  total = total_wdf(inv_addr->term);
  722.  (void) fprintf(output,"\n%s - %f -",inv_addr->term,total);
  723.  if (total < LOW_THRESHOLD) (void) fprintf(output," LOW\n");
  724.     else if (total > HIGH_THRESHOLD) (void) fprintf(output," HIGH\n");
  725.          else (void) fprintf(output," MEDIUM\n");
  726. inv_addr = inv_addr->next; /* continue with next inverted file entry */
  727. }
  728. }
  729.  
  730. /***************************************************************************
  731.  
  732.      cohesion(term1,term2)
  733.  
  734.      Returns:  float
  735.  
  736.      Purpose:  Compute the cohesion between two terms 
  737.  
  738. **/
  739.  
  740. static float cohesion(term1,term2)
  741. char term1[MAXWORD],   /* in: the two terms which are being  */
  742.      term2[MAXWORD];   /* in: compared to determine cohesion */
  743. {
  744. float l1,              /* holds # of documents associated with term1 */
  745.       l2,              /* holds # of documents associated with term2 */
  746.       common;          /* holds # of documents in common             */
  747.  
  748. get_term_data(term1,term2,&l1,&l2,&common);
  749. return(common/(sqrt(l1 * l2)));
  750. }
  751.  
  752. /***************************************************************************
  753.  
  754.      dv_all()
  755.  
  756.      Returns:  void
  757.   
  758.      Purpose:  Compute Discrimination Value (DV) for all terms in the 
  759.                database 
  760.  
  761.      Notes:    Similarity between two documents as calculated here is a
  762.                function of the number of terms in common and the number
  763.                of terms in each.  Term weights are not involved
  764.  
  765. **/
  766.  
  767. static void dv_all()
  768. {
  769. struct invert *inv_addr;     /* tracks address of current inv. file record */
  770. float DV,                    /* holds computed DV                          */
  771.       baseline;              /* holds baseline similarity                  */
  772.  
  773. /* first compute baseline similarity */
  774.  
  775. baseline = av_doc_similarity("-");  /* the dummy term '-' is used for this */
  776. (void) fprintf(output,"-----------------------------------------\n");
  777. (void) fprintf(output,"TERM                           DV\n");
  778. (void) fprintf(output,"-----------------------------------------\n");
  779. inv_addr = startinv;  /* begin at top of inverted file */
  780. while (inv_addr) {  /* if legitimate inverted file record */
  781.   DV = av_doc_similarity(inv_addr->term) - baseline;
  782.   (void) fprintf(output,"%-30s %-10.5f \n",inv_addr->term,DV);
  783.   inv_addr = inv_addr->next;  /* go to next inverted file record */
  784. }
  785. }
  786.  
  787. /***************************************************************************
  788.  
  789.      av_doc_similarity(term)
  790.  
  791.      Returns:  float
  792.  
  793.      Purpose:  Compute average similarity between each document
  794.                and the centroid of the database.  The word specified in
  795.                term is ignored during computations.
  796.  
  797. **/
  798.  
  799. static float av_doc_similarity(term)
  800. char term[MAXWORD];         /* in: term is ignored during computations  */
  801. {
  802. struct direct *dir_addr;    /* tracks current direct file record        */
  803. float dl1,                  /* holds # of terms in document             */
  804.       dl2,                  /* holds # of terms in centroid             */
  805.       common,               /* holds # of terms in common between them  */
  806.       total_sim;            /* holds total similarity between them      */
  807.  
  808. total_sim = 0.0;
  809. dir_addr = startdir; /* begin with first direct file record */
  810. while (dir_addr) {
  811.   /* get_doc_data returns #of terms in each document and #of terms in common */
  812.   get_doc_data(dir_addr,start_centroid,&dl1,&dl2,&common,term);
  813.   total_sim = total_sim + cosine(dl1,dl2,common);
  814.   dir_addr = dir_addr->next;  /* go to next direct file record */
  815. }
  816. return(total_sim/Number_of_docs);
  817. }
  818.  
  819. /***************************************************************************
  820.  
  821.      dice(term1,term2)
  822.  
  823.      Returns:  float
  824.  
  825.      Purpose:  Returns Dice's coefficient of similarity between 
  826.                any two documents 
  827.  
  828. **/ 
  829.  
  830. static float dice(term1,term2)
  831. char term1[MAXWORD],        /* in: the two terms that are being compared */
  832.      term2[MAXWORD];        /* in:                                       */ 
  833. {
  834. float l1, l2, common;
  835.  
  836. get_term_data(term1,term2,&l1,&l2,&common);
  837.  
  838. if (l1 == 0 || l2 == 0) return(0.0);
  839. return(common/(l1 + l2));
  840. }
  841.  
  842. /***************************************************************************
  843.  
  844.      cosine(l1,l2,common)
  845.  
  846.      Returns:  float
  847.  
  848.      Purpose:  Returns cosine similarity between two documents           
  849.  
  850. **/
  851.  
  852. static float cosine(l1,l2,common)
  853. float l1,                  /* in: # of terms associated with document 1 */
  854.       l2,                  /* in: # of terms associated with document 2 */
  855.       common;              /* in: # of terms in common between them     */
  856. {
  857. float temp;
  858.  
  859. if (l1 == 0 || l2 == 0) return(0.0);
  860. temp = sqrt(l1 * l2);
  861. return(common/temp);
  862. }
  863.  
  864. /***************************************************************************
  865.  
  866.      get_doc_data(p,q,l1,l2,common,index)
  867.  
  868.      Returns:  void
  869.  
  870.      Purpose:  Given two document numbers, it determines the number of
  871.      of index terms in each and in common.  It will exclude the index
  872.      term (specified as the last parameter) from consideration.  Used 
  873.      in av_doc_similarity for DV calculations.
  874.  
  875. **/
  876.  
  877. static void get_doc_data(p,q,l1,l2,common,index)
  878. char index[MAXWORD];       /* in: term to be excluded from computations */
  879. struct direct *p, *q;      /* in: addresses of two documents numbers    */
  880. float *l1, *l2;            /* out: number of terms in each document     */
  881. float *common;             /* out: number of terms in common            */
  882. {
  883. struct termlist *term_addr1, /* holds address of first docs. termlist  */
  884.                 *term_addr2; /* holds address of second docs. termlist */
  885. int count1,                  /* number of terms in first doc.          */
  886.     count2,                  /* number of terms in second doc.         */
  887.     com;                     /* number of terms in common              */
  888.  
  889. term_addr1 = p->terms;
  890. count1 = 0;  count2 = 0;  com = 0;
  891. /* first find out number of terms in document 1 & # of common terms */
  892. while (term_addr1) {
  893.   if (strncmp(term_addr1->term,index,MAXWORD)) count1 = count1 + 1; 
  894.      /* if its not the term to exclude */
  895.   term_addr2 = q->terms;
  896.   while (term_addr2) {
  897.     if (!strncmp(term_addr1->term,term_addr2->term,MAXWORD)) {
  898.          /* if the two terms are the same */
  899.         if (strncmp(term_addr1->term,index,MAXWORD)) com = com + 1; 
  900.          /* if they do not match the term to exclude */
  901.         break;
  902.     }
  903.     term_addr2 = term_addr2->nextterm;
  904.   }
  905.   term_addr1 = term_addr1->nextterm;
  906. } 
  907. /* now find out number of terms in document 2 */
  908. term_addr2 = q->terms;
  909. while (term_addr2) {
  910.   if (strncmp(term_addr2->term,index,MAXWORD)) count2 = count2 + 1; 
  911.   term_addr2 = term_addr2->nextterm;
  912. }
  913. *l1 = count1;  *l2 = count2;  *common = com;
  914. }
  915.  
  916. /***************************************************************************
  917.  
  918.     get_term_data(term1,term2,l1,l2,common)
  919.  
  920.     Returns:  void
  921.  
  922.     Purpose:  Get info regarding number of documents in common
  923.               between any two terms.
  924.  
  925. **/
  926.  
  927. static void get_term_data(term1,term2,l1,l2,common)
  928. char  term1[MAXWORD],   /* in: term 1 to be compared with               */
  929.       term2[MAXWORD];   /* in: term 2                                   */
  930. float *l1,              /* out: # of documents associated with 1st term */
  931.       *l2,              /* out: # of documents associated with 2nd term */ 
  932.       *common;          /* out: # of documents in common between them   */
  933. {
  934. struct invert *p,       /* holds address of first term in inverted file  */
  935.               *q;       /* holds address of second term in inv. file     */
  936. struct doclist *doc_ad1,/* tracks doclist for first term                 */
  937.                *doc_ad2;/* tracks doclist for second term                */
  938. int count1,             /* holds # of documents associated with 1st term */
  939.     count2,             /* holds # of documents associated with 2nd term */
  940.     com;                /* holds # of documents common between them      */
  941.  
  942. /* find addresses of both terms in the inverted file */
  943. p = find_term(term1);  q = find_term(term2);
  944. doc_ad1 = p->doc; /* obtain 1st terms doclist address */
  945. count1 = 0;  count2 = 0;  com = 0;
  946.  
  947. /* first get # of documents indexed by term 1 & # of docs. in common */
  948. while (doc_ad1) {
  949.   count1 = count1 +1;
  950.   doc_ad2 = q->doc;
  951.   while (doc_ad2) {
  952.     if (doc_ad1->doc == doc_ad2->doc) {
  953.         /* if the document numbers are the same  */
  954.         com = com +1;
  955.         break;
  956.     }
  957.     doc_ad2 = doc_ad2->nextdoc;
  958.   }
  959.   doc_ad1 = doc_ad1->nextdoc;
  960. } 
  961.  
  962. /* now get # of documents indexed by term 2 */
  963. doc_ad2 = q->doc;
  964. while (doc_ad2) {
  965.   count2 = count2 + 1;
  966.   doc_ad2 = doc_ad2->nextdoc;
  967. }
  968. *l1 = count1;  *l2 = count2;  *common = com;
  969. }
  970.  
  971. /***************************************************************************
  972.  
  973.      *find_term(term)
  974.  
  975.      Returns:  address of a struct invert record
  976.  
  977.      Purpose:  search for a specified term in the inverted file & 
  978.                return address of the record
  979.  
  980. **/
  981.  
  982. struct invert *find_term(term)
  983. char term[MAXWORD];          /* in: term to be located in inverted file   */
  984. {
  985. struct invert *inv_addr;     /* tracks addr. of current rec. in inv. file */
  986. inv_addr = startinv;         /* begin at top of inv. file                 */
  987.  
  988. while(inv_addr) {
  989.   if (!strcmp(term,inv_addr->term)) {return(inv_addr);}
  990.   inv_addr = inv_addr->next;
  991. }
  992. (void) fprintf(output,"Findterm routine:  Term %s not found\n",term);
  993. return(NULL);
  994. }
  995.  
  996. /***************************************************************************
  997.  
  998.      *get_mem_direct()
  999.  
  1000.      Returns:  address of a struct direct record
  1001.  
  1002.      Purpose:  dynamically obtain enough memory to store 1 direct record 
  1003.  
  1004. **/
  1005.  
  1006. static struct direct *get_mem_direct()
  1007. {
  1008. struct direct *record;
  1009.  
  1010. record = (struct direct *)malloc(sizeof(directfile));
  1011. if (!record) {
  1012.     (void) fprintf(output,"\nout of memory\n");
  1013.     exit(0);
  1014. }
  1015. return(record);
  1016. }
  1017.  
  1018. /***************************************************************************
  1019.  
  1020.      *get_mem_termlist()
  1021.  
  1022.      Returns:  address of a struct termlist record
  1023.  
  1024.      Purpose:  dynamically obtain enough memory to store one termlist record 
  1025.  
  1026. **/
  1027.  
  1028. static struct termlist *get_mem_termlist()
  1029. {
  1030. struct termlist *record;
  1031.  
  1032. record = (struct termlist *)malloc(sizeof(termlistfile));
  1033. if (!record) {
  1034.     (void) fprintf(output,"\nout of memory\n");
  1035.     exit(0);
  1036. }
  1037. return(record);
  1038. }
  1039.  
  1040. /***************************************************************************
  1041.  
  1042.      *get_mem_invert()
  1043.  
  1044.      Returns:  address of a struct invert record
  1045.  
  1046.      Purpose:  dynamically obtain enough memory to store one inverted 
  1047.                file record 
  1048.  
  1049. **/
  1050.  
  1051. static struct invert *get_mem_invert()
  1052. {
  1053. struct invert *record;
  1054.  
  1055. record = (struct invert *)malloc(sizeof(invfile));
  1056. if (!record) {
  1057.     (void) fprintf(output,"\nout of memory\n");
  1058.     exit(0);
  1059. }
  1060. return(record);
  1061. }
  1062.  
  1063. /***************************************************************************
  1064.  
  1065.      *get_mem_doclist()
  1066.  
  1067.      Returns:  address of a struct doclist record
  1068.  
  1069.      Purpose:  dynamically obtain enough memory to store one doclist 
  1070.                record 
  1071.  
  1072. **/
  1073.  
  1074. static struct doclist *get_mem_doclist()
  1075. {
  1076. struct doclist *record;
  1077.  
  1078. record = (struct doclist *)malloc(sizeof(doclistfile));
  1079. if (!record) {
  1080.     (void) (void) fprintf(output,"\nout of memory\n");
  1081.     exit(0);
  1082. }
  1083. return(record);
  1084. }
  1085.  
  1086.